package com.example.leetcode.prcatice;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class OfferII77 {

    public ListNode sortList(ListNode head) {
        if (head == null){
            return head;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x.val));
        ListNode pre = head;
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while (pre != null){
            queue.offer(pre);
            pre = pre.next;
        }
        int size = queue.size();
        for (int i =0;i<size;i++){
            System.out.println();
            ListNode poll = queue.poll();
            tail.next = poll;
            tail = poll;
        }
        tail.next = null;
        return newHead.next;
    }
}


class DemoOfferII77{
  public static void main(String[] args) {
    ListNode head = new ListNode(-1);
    head.next = new ListNode(0);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(0);
    OfferII77 o = new OfferII77();
    ListNode listNode = o.sortList(head);
    while (listNode != null){
      System.out.println("val ="+listNode.val);
      listNode = listNode.next;
    }
  }
}